package bTree.LeetCode;


public class 冗余连接 {
    int []father=null;
    public int[] findRedundantConnection(int[][] edges) {
        //初始化
        int length = edges.length;
        father=new int[length+1];
        init();
        for (int[] edge : edges) {
            boolean join = join(edge[0], edge[1]);
            if (!join){
                return new int[]{edge[0],edge[1]};
            }
        }
        return null;
    }

    /**
     * 初始化。每个值的父亲节点是自己本身
     * @param
     */
    private void init() {
        for(int i=1;i<father.length;i++){
            father[i]=i;
        }
    }

    /**
     * 查询祖先节点
     * @param u
     * @return
     */
    private int find(int u){
        return father[u]==u?u:(father[u]=find(father[u]));//压缩状态
    }

    /**
     * 判断是否在同一集合
     * @param u
     * @param v
     * @return
     */
    private boolean isSame(int u,int v){
        int i = find(u);
        int j=find(v);
        return i==j;
    }

    /**
     * 拼接节点
     * @param u
     * @param v
     */
    private boolean join(int u,int v){
        int i = find(u);
        int j=find(v);
        if(i==j){
            return false;
        }
        father[j]=i;
        return true;
    }
}